// 链表中的倒数第K个结点
// 采用两个指针，一个在前面移动K-1步，另一个开始移动，当前面一个达到尾结点的时候，另一个指向倒数第K个结点
#include "LinkedList.h"

ListNode * FindKthNodeToTail(ListNode * pListHead, unsigned int K)
{
    if (pListHead == NULL || K == 0)
        return NULL;

    ListNode * pAhead = pListHead;
    ListNode * pBehind = NULL;

    for(unsigned int i = 0; i < K - 1; ++ i)
    {
        // 链表长度小于K
        if (pAhead->m_pNext != NULL)
            pAhead = pAhead->m_pNext;
        else
            return NULL;
    }
    pBehind = pListHead;
    while (pAhead->m_pNext != NULL)
    {
        pAhead = pAhead->m_pNext;
        pBehind = pBehind->m_pNext;
    }
    return pBehind;
}

// Find Mid-Node of a LinkedList
// 思路：采用两个指针，同时从pListHead出发，一个指针一次走一步，一个一次走两步。当第一个走到末尾的时候，走的慢的正好处于链表中间。
ListNode * FindMidNodeOfList(ListNode * pListHead)
{
    if (pListHead == NULL)
        return NULL;
    ListNode * pAhead = pListHead;
    ListNode * pBehind = pListHead;

    while (pAhead->m_pNext != NULL)
    {
        pAhead = pAhead->m_pNext;
        // attention
        if (pAhead->m_pNext != NULL)
            pAhead = pAhead->m_pNext;
        else
            return pBehind;
        pBehind = pBehind->m_pNext;
    }
    return pBehind;
    
}

// 判断一个链表是否是环形
// 思路：两个指针同时出发，一个一次走一步，一次一个走两步。如果走的快的指针赶上慢的指针，链表就形成环形。
// 如果走的快的指针走到末尾都没有追上第一个指针，链表不是环形。
bool IsCircleList(ListNode * pListHead)
{
    if (pListHead == NULL)
        return false;
    ListNode * pAhead = pListHead;
    ListNode * pBehind = pListHead;
    
    while (pAhead->m_pNext != NULL)
    {
        pAhead = pAhead->m_pNext;
        if (pAhead == pBehind)
            return true;
        if(pAhead->m_pNext != NULL)
            pAhead = pAhead->m_pNext;
        if (pAhead == pBehind)
            return true;
        pBehind = pBehind->m_pNext;
    }
    return false;
}

int main(int argc, char * argv[])
{
    ListNode * pListHead = NULL;
    for(int i = 0; i < 2; ++i)
        AddToTail(&pListHead, i);
    PrintList(pListHead);

    // Find KthToTail Node
    unsigned int K = atoi(argv[argc-1]);
    cout << K << endl;
    ListNode * pKthNode = FindKthNodeToTail(pListHead, K);
    PrintListNode(pKthNode);
    cout << endl;
    DeleteNode(&pListHead, pKthNode);
    PrintList(pListHead);
    
    // Find MidNode
    ListNode * pMidNode = FindMidNodeOfList(pListHead);
    PrintListNode(pMidNode);
    cout << endl;
    DeleteNode(&pListHead, pMidNode);
    PrintList(pListHead);

    // IsCircleList
    cout << "LinkedList is Circled: " << IsCircleList(pListHead) << endl;
    // 找到last Node并指向pListHead,形成环形链表
    ListNode * pLastNode = FindKthNodeToTail(pListHead, 1);
    if (pLastNode == NULL)
    {
        cout << "List is empty" << endl;
        return 0;
    }
    pLastNode->m_pNext = pListHead;
    cout << "LinkedList is Circled: " << IsCircleList(pListHead) << endl;
    
    return 0;
}
